//
//  Problem861.swift
//  TestProject
//
//  Created by 武侠 on 2021/5/20.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 861. 翻转矩阵后的得分
 有一个二维矩阵 A 其中每个元素的值为 0 或 1 。

 移动是指选择任一行或列，并转换该行或列中的每一个值：将所有 0 都更改为 1，将所有 1 都更改为 0。
 在做出任意次数的移动后，将该矩阵的每一行都按照二进制数来解释，矩阵的得分就是这些数字的总和。
 返回尽可能高的分数。

 示例：
   输入：[[0,0,1,1],[1,0,1,0],[1,1,0,0]]
   输出：39
   解释：
     转换为 [[1,1,1,1],[1,0,0,1],[1,1,1,1]]
     0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39

 提示：
     1 <= A.length <= 20
     1 <= A[0].length <= 20
     A[i][j] 是 0 或 1
 */
@objcMembers class Problem861: NSObject {
    func solution() {
        print(matrixScore([[0,0,1,1],[1,0,1,0],[1,1,0,0]]))
    }
    
    /*
     最高的分数：
     1: 首先让每一行的第一个全都变成1：如果一行的第一个数不是1，那么反转该行
     2: 从第二列开始遍历：如果这一列的1的个数 小于 0，转换一下
     */
    func matrixScore(_ grid: [[Int]]) -> Int {
        var n = grid.count * (1 << (grid[0].count-1))
        for j in 1..<grid[0].count {
            var n1 = 0      // 统计1的个数
            for t in 0..<grid.count {
                if grid[t][0] == 1, grid[t][j] == 1 {  // 当前行不需要反转
                    n1 += 1
                } else if grid[t][0] == 0, grid[t][j] == 0 { // 当前行需要反转
                    n1 += 1
                }
            }
            if grid.count - n1 > n1 {   // 当前列需要转换一下
                n1 = grid.count - n1
            }
            n += n1 * (1 << (grid[0].count-j-1))
        }
        
        return n
    }
}
